{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# k-近邻算法\n",
    "- 优点： 精度高、 对异常值不敏感、 无数据输入假定。\n",
    "- 缺点： 计算复杂度高、 空间复杂度高。 \n",
    "- 适用数据范围： 数值型和标称型。\n",
    "\n",
    "一般来说， 我们只选择样本数据集中前k个最相似的数据， 这就是k-近邻算法中k的出处， 通常k是不大于20的整数。 最后， 选择k个最相似数据中出现次数最多的分类， 作为新数据的分类。\n",
    "\n",
    "# k近邻算法的一般流程\n",
    "1. 收集数据： 可以使用任何方法。\n",
    "2. 准备数据： 距离计算所需要的数值， 最好是结构化的数据格式。\n",
    "3. 分析数据： 可以使用任何方法。\n",
    "4. 训练算法： 此步骤不适用于k近邻算法。\n",
    "5. 测试算法： 计算错误率。\n",
    "6. 使用算法： 首先需要输入样本数据和结构化的输出结果， 然后运行\n",
    "k近邻算法判定输入数据分别属于哪个分类， 最后应用对计算出的分类执行后续的处理。\n",
    "\n",
    "k近邻算法是基于实例的学习， 使用算法时我们必须有接近实际数据的训练样本数据。 k近邻算法必须保存全部数据集， 如果训练数据集的很大， 必须使用大量的存储空间。 此外， 由于必须对数据集中的每个数据计算距离值， 实际使用时可能非常耗时。\n",
    "K近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息， 因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 1.   1.1]\n",
      " [ 1.   1. ]\n",
      " [ 0.   0. ]\n",
      " [ 0.   0.1]]\n",
      "['A', 'A', 'B', 'B']\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def createDataSet():\n",
    "    group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])\n",
    "    labels = ['A','A','B','B']\n",
    "    return group, labels\n",
    "\n",
    "group,labels = createDataSet()\n",
    "print(group)\n",
    "print(labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1.48660687  1.41421356  0.          0.1       ]\n",
      "[2 3 1 0]\n",
      "B\n"
     ]
    }
   ],
   "source": [
    "import operator\n",
    "\n",
    "def classify0(inX, dataSet, labels, k):\n",
    "    dataSetSize = dataSet.shape[0]\n",
    "    #❶（以下三行） 距离计算\n",
    "    # np.tile(a,(2,1))就是把a先沿x轴（就这样称呼吧）复制1倍，即没有复制，仍然是 [0,1,2],再把结果沿y方向复制2倍\n",
    "    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet  #np.tile把数组沿各个方向复制\n",
    "    sqDiffMat = diffMat**2\n",
    "    sqDistances = sqDiffMat.sum(axis=1)\n",
    "    distances = sqDistances**0.5\n",
    "    print(distances)\n",
    "    sortedDistIndicies = distances.argsort()\n",
    "    print(sortedDistIndicies)\n",
    "    classCount={}\n",
    "    #❷ （以下两行） 选择距离最小的k个点,统计频率\n",
    "    for i in range(k):\n",
    "        voteIlabel = labels[sortedDistIndicies[i]]\n",
    "        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1\n",
    "    #❸ 排序，字典根据词频降序\n",
    "    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True)        \n",
    "    return sortedClassCount[0][0]\n",
    "\n",
    "print(classify0([0,0], group, labels, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
